{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 302,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from numba import njit \n",
    "from collections import namedtuple\n",
    "import random\n",
    "# Item = namedtuple(\"Item\", ['index', 'value', 'weight'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##for fun haha\n",
    "# !pip install jupyterthemes\n",
    "# !jt -t chesterish"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 303,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('gc_50_3.txt') as input_data:\n",
    "    lines= list(input_data)\n",
    "\n",
    "    first_line = lines[0].split()\n",
    "    node_count = int(first_line[0])\n",
    "    edge_count = int(first_line[1])\n",
    "\n",
    "    edges = []\n",
    "    for i in range(1, edge_count + 1):\n",
    "        line = lines[i]\n",
    "        parts = line.split()\n",
    "        edges.append((int(parts[0]), int(parts[1])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "test=[(1,2), (3,4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 304,
   "metadata": {},
   "outputs": [],
   "source": [
    "constraint_order=[]\n",
    "\n",
    "##first degree constraint_order\n",
    "for i in range(node_count):\n",
    "    count=0\n",
    "    for k in edges:\n",
    "        if i in k:\n",
    "            count+=1\n",
    "    constraint_order.append((i, count))\n",
    "\n",
    "## second degree constraint_order\n",
    "second_constraint_order=[]\n",
    "for i in range(node_count):\n",
    "    count=0\n",
    "    for k in edges:\n",
    "        if i in k:\n",
    "            for index in range(len(constraint_order)):\n",
    "                if constraint_order[index][0]==k[1-k.index(i)]:\n",
    "                    count+=constraint_order[index][1]\n",
    "    second_constraint_order.append((i, count))\n",
    "\n",
    "constraint_order=sorted(second_constraint_order, key=lambda x: x[1])\n",
    "\n",
    "\n",
    "##sometimes second degree works better;\n",
    "## generally more complex data, better second degree performs.\n",
    "\n",
    "\n",
    "fixed_order=[]\n",
    "for i in constraint_order:\n",
    "    fixed_order.append(i[0])\n",
    "\n",
    "combined_edges=[]\n",
    "for i in range(node_count):\n",
    "    close_nodes=[]\n",
    "    for k in edges:\n",
    "        if i in k:\n",
    "            close_nodes.append(k[1-k.index(i)])\n",
    "    combined_edges.append(close_nodes)\n",
    "    \n",
    "    \n",
    "total_color=node_count-1  ### at most \n",
    "table=np.zeros((node_count, total_color))\n",
    "\n",
    "# total_color=8\n",
    "# table=np.zeros((node_count, total_color))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 7, 16, 17, 12, 14, 1, 8, 5, 3, 15, 19, 6, 13, 18, 2, 4, 9, 11, 10]"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed_order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 305,
   "metadata": {},
   "outputs": [],
   "source": [
    "##0: haven't tries\n",
    "##1: decision\n",
    "##-1: not feasible\n",
    "while constraint_order:\n",
    "    constraint_pair= constraint_order.pop()\n",
    "    node=constraint_pair[0]\n",
    "    available_color_list = np.where(table[node]==0)  ##find all available colors\n",
    "\n",
    "    \n",
    "    if 0 in table[node]:\n",
    "        color=available_color_list[0][0]  ##find the first avaiable color\n",
    "        table[node][color]=1   ## color this node\n",
    "        ##for other attched nodes, they cannot use the same color\n",
    "                \n",
    "        check=True\n",
    "        for other in combined_edges[node]:\n",
    "            if 1 not in table[other]:\n",
    "                if np.where(table[other]==0)[0].size==1 and np.where(table[other]==0)[0][0]==color:\n",
    "                    check=False\n",
    "        \n",
    "        if check:\n",
    "            for other in combined_edges[node]:\n",
    "                if 1 not in table[other]:\n",
    "                    table[other][color]=-1\n",
    "        else:\n",
    "            table[node][color]=-1\n",
    "            constraint_order.append((node, _))\n",
    "      \n",
    "    \n",
    "\n",
    "## This whole part is for feasbility checking\n",
    "## for some reasons, it's not working\n",
    "\n",
    "#     else:\n",
    "#         ##recover the current node constraint\n",
    "#         node_constraint= np.zeros(total_color)\n",
    "#         previous_nodes= fixed_order[fixed_order.index(node)+1:]\n",
    "#         for previous_node in previous_nodes:\n",
    "#             node_constraint[np.where(table[previous_node]==1)[0][0]]=-1\n",
    "#         table[node]=node_constraint\n",
    "\n",
    "        \n",
    "#         previous_node=fixed_order[fixed_order.index(node)+1]\n",
    "#         previous_color=np.where(table[previous_node]==1)[0][0]\n",
    "#         table[previous_node][previous_color]= -1\n",
    "#         for other in combined_edges[previous_node]:\n",
    "#             if 1 not in table[other]:\n",
    "#                 adjust=False\n",
    "#                 for k in previous_nodes[1:]:\n",
    "#                     if np.where(table[k]==1)[0][0]==previous_color and other in combined_edges[k]:\n",
    "#                         adjust=True\n",
    "#                 if adjust:\n",
    "#                     table[other][previous_color]=0\n",
    "                \n",
    "        \n",
    "#         constraint_order.append(constraint_pair)\n",
    "#         constraint_order.append((previous_node, _))\n",
    "#         print('node', node)\n",
    "#         print('previous node', previous_node)\n",
    "#         print('previous_color', previous_color)\n",
    "#         print(len(constraint_order), ' nodes left')\n",
    "#     if node==24:\n",
    "#         print()\n",
    "\n",
    "    \n",
    "#     if len(constraint_order)==node_count:\n",
    "#         print('fail')\n",
    "    \n",
    "# #     color=available_color_list[0][0]  ##find the first avaiable color\n",
    "# #     table[node][color]=1   ## color this node\n",
    "# #     ##for other attched nodes, they cannot use the same color\n",
    "# #     for other in combined_edges[node]:\n",
    "# #         table[other][color]=-1\n",
    "\n",
    "output=[]\n",
    "for i in range(node_count):\n",
    "    output.append(np.where(table[i]==1)[0][0])\n",
    "\n",
    "# total_color=max(output)+1    \n",
    "total_color=len(set(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 306,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 306,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total_color"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 322,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total_color 7\n",
      "bad nodes are [10, 14, 15, 22, 35, 46]\n",
      "can't be better\n",
      "total_color 7\n",
      "bad nodes are [10, 14, 15, 22, 35, 46]\n",
      "can't be better\n",
      "total_color 7\n",
      "bad nodes are [10, 14, 15, 22, 35, 46]\n",
      "can't be better\n",
      "total_color 7\n",
      "bad nodes are [3, 6, 12, 27, 34, 42]\n",
      "can't be better\n",
      "total_color 7\n",
      "bad nodes are [17, 19, 25, 36, 40, 41]\n",
      "bad nodes are [35, 8, 46, 20, 29]\n",
      "bad nodes are [40, 25, 19, 36]\n",
      "bad nodes are [49, 4, 29, 46]\n",
      "bad nodes are [40, 17, 36, 6]\n",
      "bad nodes are [32, 20, 45, 46]\n",
      "bad nodes are [40, 49, 17, 25]\n",
      "bad nodes are [32, 4, 45]\n",
      "bad nodes are [40, 35, 36]\n",
      "bad nodes are [2, 45, 7]\n",
      "bad nodes are [3, 35, 36]\n",
      "bad nodes are [2, 45, 7]\n",
      "bad nodes are [40, 35, 36]\n",
      "bad nodes are [49, 20, 45]\n",
      "bad nodes are [40, 35, 7]\n",
      "bad nodes are [32, 3, 4]\n",
      "bad nodes are [43, 35, 5]\n",
      "bad nodes are [8, 3, 45]\n",
      "bad nodes are [41, 35, 7]\n",
      "bad nodes are [8, 49, 32]\n",
      "bad nodes are [35, 43, 36]\n",
      "bad nodes are [32, 8, 45]\n",
      "bad nodes are [43, 35, 36]\n",
      "bad nodes are [8, 32, 2]\n",
      "bad nodes are [41, 35, 9]\n",
      "bad nodes are [8, 2, 45]\n",
      "bad nodes are [41, 35, 36]\n",
      "bad nodes are [32, 33, 45]\n",
      "bad nodes are [41, 35, 36]\n",
      "bad nodes are [8, 49, 45]\n",
      "bad nodes are [35, 43, 36]\n",
      "bad nodes are [32, 8, 2]\n",
      "bad nodes are [41, 35, 9]\n",
      "bad nodes are [8, 32, 2]\n",
      "bad nodes are [49, 43, 36]\n",
      "bad nodes are [32, 2, 4]\n",
      "bad nodes are [40, 49, 9]\n",
      "bad nodes are [32, 2, 7]\n",
      "bad nodes are [3, 35, 36]\n",
      "bad nodes are [2, 45, 5]\n",
      "bad nodes are [3, 9, 35]\n",
      "bad nodes are [32, 2, 5]\n",
      "bad nodes are [3, 35, 36]\n",
      "bad nodes are [49, 45, 7]\n",
      "bad nodes are [3, 35]\n",
      "bad nodes are [32, 5]\n",
      "bad nodes are [3, 36]\n",
      "bad nodes are [42, 5]\n",
      "bad nodes are [10, 3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [5]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [5]\n",
      "bad nodes are [3]\n",
      "bad nodes are [5]\n",
      "bad nodes are [7]\n",
      "bad nodes are [5]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [9]\n",
      "bad nodes are [3]\n",
      "bad nodes are [5]\n",
      "bad nodes are [7]\n",
      "bad nodes are [5]\n",
      "bad nodes are [7]\n",
      "bad nodes are [5]\n",
      "bad nodes are [0]\n",
      "total_color 6\n",
      "bad nodes are [6, 7, 10, 12, 27, 34, 36]\n",
      "can't be better\n",
      "total_color 6\n",
      "bad nodes are [8, 14, 15, 22, 42, 45, 46]\n",
      "can't be better\n",
      "total_color 6\n",
      "bad nodes are [6, 7, 10, 12, 27, 34, 36]\n",
      "can't be better\n",
      "total_color 6\n",
      "bad nodes are [6, 7, 10, 12, 34, 36]\n",
      "can't be better\n",
      "total_color 6\n",
      "bad nodes are [6, 7, 10, 12, 34, 36]\n",
      "can't be better\n",
      "total_color 6\n",
      "bad nodes are [6, 7, 10, 12, 34, 36]\n",
      "can't be better\n",
      "6 colors True\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    output= local_search(output)\n",
    "print(len(set(output)), 'colors', check_output(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 7, 3, 5, 1, 3, 0, 5, 5, 4, 0, 3, 0, 4, 4, 0, 6, 5, 3, 2, 2, 4, 1, 1, 6, 1, 3, 4, 2, 2, 1, 2, 2, 3, 1, 6, 5, 7, 0, 6, 6, 0, 0, 1, 0, 4, 1, 2, 5]\n"
     ]
    }
   ],
   "source": [
    "print(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## we know the optimal is 6; the following part is the local search to reach the optimal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {},
   "outputs": [],
   "source": [
    "bad_nodes= [i for i, x in enumerate(output) if x ==total_color-1 ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 38]"
      ]
     },
     "execution_count": 291,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bad_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[36]"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[conflict_node for conflict_node in combined_edges[2] if output[conflict_node]==6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bad nodes are [2, 38]\n",
      "currently dealling with bad node 2\n",
      "bad_node 2 possible_new_colors [0, 1, 5, 6] randomly pick 5\n",
      "new bad [9]\n",
      "currently dealling with bad node 38\n",
      "bad_node 38 possible_new_colors [1, 2, 3, 4, 6] randomly pick 2\n",
      "new bad [9, 48]\n",
      "bad nodes are [48, 9]\n",
      "currently dealling with bad node 48\n",
      "bad_node 48 possible_new_colors [0, 2, 5, 6] randomly pick 2\n",
      "new bad [38]\n",
      "currently dealling with bad node 9\n",
      "bad_node 9 possible_new_colors [5, 6] randomly pick 6\n",
      "new bad [38, 25]\n",
      "bad nodes are [25, 38]\n",
      "currently dealling with bad node 25\n",
      "bad_node 25 possible_new_colors [4, 5, 6] randomly pick 4\n",
      "new bad [46]\n",
      "currently dealling with bad node 38\n",
      "bad_node 38 possible_new_colors [1, 2, 3, 4, 5] randomly pick 4\n",
      "new bad [46, 10]\n",
      "bad nodes are [10, 46]\n",
      "currently dealling with bad node 10\n",
      "bad_node 10 possible_new_colors [1, 3, 4] randomly pick 3\n",
      "new bad [19]\n",
      "currently dealling with bad node 46\n",
      "bad_node 46 possible_new_colors [2, 3, 4] randomly pick 2\n",
      "new bad [19, 33]\n",
      "bad nodes are [33, 19]\n",
      "currently dealling with bad node 33\n",
      "bad_node 33 possible_new_colors [2, 5] randomly pick 2\n",
      "new bad [46]\n",
      "currently dealling with bad node 19\n",
      "bad_node 19 possible_new_colors [2, 3, 5, 6] randomly pick 2\n",
      "new bad [46, 29]\n",
      "bad nodes are [29, 46]\n",
      "currently dealling with bad node 29\n",
      "bad_node 29 possible_new_colors [5] randomly pick 5\n",
      "new bad []\n",
      "currently dealling with bad node 46\n",
      "bad_node 46 possible_new_colors [2, 3, 4] randomly pick 4\n",
      "new bad [25]\n",
      "bad nodes are [25]\n",
      "currently dealling with bad node 25\n",
      "bad_node 25 possible_new_colors [4, 5, 6] randomly pick 6\n",
      "new bad [9]\n",
      "bad nodes are [9]\n",
      "currently dealling with bad node 9\n",
      "bad_node 9 possible_new_colors [5, 6] randomly pick 6\n",
      "new bad [25]\n",
      "bad nodes are [25]\n",
      "currently dealling with bad node 25\n",
      "bad_node 25 possible_new_colors [4, 5, 6] randomly pick 5\n",
      "new bad [1]\n",
      "bad nodes are [1]\n",
      "currently dealling with bad node 1\n",
      "bad_node 1 possible_new_colors [6] randomly pick 6\n",
      "new bad []\n"
     ]
    }
   ],
   "source": [
    "bad_nodes= [i for i, x in enumerate(output) if x ==total_color-1 ]\n",
    "while bad_nodes:\n",
    "    print('bad nodes are', bad_nodes)\n",
    "    new_bad=[]\n",
    "    \n",
    "    for bad_node in bad_nodes:\n",
    "        print('currently dealling with bad node', bad_node)\n",
    "        losses= []\n",
    "        for new_color in range(total_color-1):\n",
    "            losses.append(len([conflict_node for conflict_node in combined_edges[bad_node] if output[conflict_node]==new_color]))\n",
    "        possible_new_colors= [new_color for new_color, loss in enumerate(losses) if losses[new_color]==min(losses)]\n",
    "        new_color=random.choice(possible_new_colors)\n",
    "        print('bad_node',bad_node, 'possible_new_colors', possible_new_colors, 'randomly pick', new_color)\n",
    "        output[bad_node]=new_color\n",
    "        new_bad+=[conflict_node for conflict_node in combined_edges[bad_node] if output[conflict_node]==new_color]\n",
    "        print('new bad', new_bad)\n",
    "    bad_nodes=list(set(new_bad))\n",
    "total_color=len(set(output))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "metadata": {},
   "outputs": [],
   "source": [
    "def local_search(output):\n",
    "    \n",
    "    total_color=len(set(output))\n",
    "    print('total_color', total_color)\n",
    "    \n",
    "    \n",
    "    \n",
    "    color_count=[output.count(i) for i in range(total_color)]\n",
    "    \n",
    "    possible_deleted_colors= [color for color in range(total_color) if color_count[color]==min(color_count)]\n",
    "    \n",
    "    random.shuffle(possible_deleted_colors)\n",
    "    for deleted_color in possible_deleted_colors:\n",
    "        original_output=[]\n",
    "        for i in output:\n",
    "            original_output.append(i)\n",
    "            \n",
    "        bad_nodes= [i for i, x in enumerate(output) if x ==deleted_color ]\n",
    "        while bad_nodes:\n",
    "            print('bad nodes are', bad_nodes)\n",
    "            new_bad=[]\n",
    "\n",
    "            for bad_node in bad_nodes:\n",
    "#                 print('currently dealling with bad node', bad_node)\n",
    "                losses= []\n",
    "                for new_color in range(total_color-1):\n",
    "                    losses.append(len([conflict_node for conflict_node in combined_edges[bad_node] if output[conflict_node]==new_color]))\n",
    "                possible_new_colors= [new_color for new_color, loss in enumerate(losses) if losses[new_color]==min(losses)]\n",
    "                new_color=random.choice(possible_new_colors)\n",
    "#                 print('bad_node',bad_node, 'possible_new_colors', possible_new_colors, 'randomly pick', new_color)\n",
    "                output[bad_node]=new_color\n",
    "                new_bad+=[conflict_node for conflict_node in combined_edges[bad_node] if output[conflict_node]==new_color]\n",
    "#                 print('new bad', new_bad)\n",
    "            bad_nodes=list(set(new_bad))\n",
    "        \n",
    "        if check_output(output)==False:\n",
    "            output=orginal_output\n",
    "        else:\n",
    "            break;\n",
    "            \n",
    "    if len(set(output))==total_color:\n",
    "        print('''can't be better''')\n",
    "        return output\n",
    "    else:\n",
    "        return local_search(output)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 293,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total_color 8\n",
      "bad nodes are [2, 38]\n",
      "bad nodes are [41, 36]\n",
      "bad nodes are [49, 22]\n",
      "bad nodes are [41]\n",
      "bad nodes are [33]\n",
      "bad nodes are [17]\n",
      "bad nodes are [8]\n",
      "total_color 7\n",
      "bad nodes are [3, 6, 12, 19, 27, 34]\n",
      "can't be better\n"
     ]
    }
   ],
   "source": [
    "new_output=local_search(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 301,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total_color"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 8, 8, 6, 6, 8, 6]"
      ]
     },
     "execution_count": 250,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[output.count(color) for color in range(total_color)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## check the output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_output(output):\n",
    "    for (a,b) in edges:\n",
    "        if output[a]==output[b]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (a,b) in edges:\n",
    "    if output[a]==output[b]:\n",
    "        print('fail', a, b)\n",
    "print('success')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First Version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_it(input_data):\n",
    "    import numpy as np\n",
    "    import pandas as pd\n",
    "    from numba import njit \n",
    "    from collections import namedtuple\n",
    "\n",
    "    # Modify this code to run your optimization algorithm\n",
    "\n",
    "    # parse the input\n",
    "    lines = input_data.split('\\n')\n",
    "\n",
    "    first_line = lines[0].split()\n",
    "    node_count = int(first_line[0])\n",
    "    edge_count = int(first_line[1])\n",
    "\n",
    "    edges = []\n",
    "    for i in range(1, edge_count + 1):\n",
    "        line = lines[i]\n",
    "        parts = line.split()\n",
    "        edges.append((int(parts[0]), int(parts[1])))\n",
    "\n",
    "    # solution\n",
    "    constraint_order=[]\n",
    "    for i in range(node_count):\n",
    "        count=0\n",
    "        for k in edges:\n",
    "            if i in k:\n",
    "                count+=1\n",
    "        constraint_order.append((i, count))\n",
    "\n",
    "    constraint_order=sorted(constraint_order, key=lambda x: x[1])\n",
    "\n",
    "    fixed_order=[]\n",
    "    for i in constraint_order:\n",
    "        fixed_order.append(i[0])\n",
    "\n",
    "    combined_edges=[]\n",
    "    for i in range(node_count):\n",
    "        close_nodes=[]\n",
    "        for k in edges:\n",
    "            if i in k:\n",
    "                close_nodes.append(k[1-k.index(i)])\n",
    "        combined_edges.append(close_nodes)\n",
    "    \n",
    "    \n",
    "    total_color=node_count-1  ### at most \n",
    "    table=np.zeros((node_count, total_color))\n",
    "\n",
    "\n",
    "\n",
    "    ###loop and search\n",
    "##0: haven't tries\n",
    "##1: decision\n",
    "##-1: not feasible\n",
    "    while constraint_order:\n",
    "        constraint_pair= constraint_order.pop()\n",
    "        node=constraint_pair[0]\n",
    "        current_node_constraint= table[node]\n",
    "        available_color_list = np.where(table[node]==0)  ##find all available colors\n",
    "    \n",
    "        if 0 in table[node]:\n",
    "            color=available_color_list[0][0]  ##find the first avaiable color\n",
    "            table[node][color]=1   ## color this node\n",
    "            ##for other attched nodes, they cannot use the same color\n",
    "            for other in combined_edges[node]:\n",
    "                if 1 not in table[other]:\n",
    "                    table[other][color]=-1      \n",
    "            \n",
    "        else:\n",
    "            previous_node=fixed_order[fixed_order.index(node)+1]\n",
    "            previous_color=np.where(table[previous_node]==1)[0][0]\n",
    "            table[previous_node][previous_color]= -1\n",
    "            for other in combined_edges[previous_node]:\n",
    "                if 1 not in table[other] and other!=node:\n",
    "                    table[other][previous_color]=0\n",
    "            table[node]=current_node_constraint\n",
    "        \n",
    "            constraint_order.append(constraint_pair)\n",
    "            constraint_order.append((previous_node, _))\n",
    "\n",
    "\n",
    "    output=[]\n",
    "    for i in range(node_count):\n",
    "        output.append(np.where(table[i]==1)[0][0])\n",
    "\n",
    "    total_color=len(set(output))  \n",
    "\n",
    "\n",
    "    # prepare the solution in the specified output format\n",
    "    output_data = str(total_color) + ' ' + str(0) + '\\n'\n",
    "    output_data += ' '.join(map(str, output))\n",
    "\n",
    "    return output_data\n",
    "\n",
    "\n",
    "import sys\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    import sys\n",
    "    if len(sys.argv) > 1:\n",
    "        file_location = sys.argv[1].strip()\n",
    "        with open(file_location, 'r') as input_data_file:\n",
    "            input_data = input_data_file.read()\n",
    "        print(solve_it(input_data))\n",
    "    else:\n",
    "        print('This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/gc_4_1)')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
